/*
 * @lc app=leetcode.cn id=72 lang=javascript
 *
 * [72] 编辑距离
 */

// @lc code=start
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const m = word1.length;
  const n = word2.length;

  if (m === 0 || n === 0) return Math.abs(m - n);

  // 将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。
  const minStep = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  // 从空变为word2的最少操作数
  for (let x = 0; x <= n; x++) minStep[0][x] = x;
  // 从word1变为空的最少操作数
  for (let x = 0; x <= m; x++) minStep[x][0] = x;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) minStep[i][j] = minStep[i - 1][j - 1];
      else
        minStep[i][j] =
          Math.min(
            minStep[i][j - 1],
            minStep[i - 1][j],
            minStep[i - 1][j - 1]
          ) + 1;
    }
  }
  return minStep[m][n];
};
// @lc code=end
